정렬되지 않은 배열을 처리하는 것보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?

당신은 분기 예측 실패의 희생자입니다.
분기 예측이란 무엇입니까?
철도 교차로를 고려하십시오.
Wikimedia Commons를 통해 Mecanismo의 이미지. CC-By-SA 3.0 라이선스에 따라 사용됩니다.
이제 논쟁을 위해 이것이 장거리 또는 무선 통신 이전 인 1800 년대로 거슬러 올라간다고 가정합니다.
당신은 교차로의 운영자이고 기차가 오는 소리를 듣습니다. 당신은 그것이 어느 방향으로 가야할지 전혀 모릅니다. 운전자에게 원하는 방향을 물어보기 위해 기차를 멈 춥니 다. 그런 다음 스위치를 적절하게 설정합니다.
기차는 무겁고 관성이 많습니다. 그래서 그들은 시작하고 느리게하는 데 영원히 걸립니다.
더 좋은 방법이 있습니까? 기차가 어느 방향으로 갈지 짐작하세요!
맞히면 계속됩니다.
잘못 추측하면 기장이 멈추고 뒤로 물러나고 스위치를 켜라고 소리를 지 릅니다. 그런 다음 다른 경로로 다시 시작할 수 있습니다.
매번 맞히면 기차가 멈출 필요가 없습니다. 너무 자주 잘못 추측하면 기차는 정지, 백업 및 재시작에 많은 시간을 소비합니다.
if 문을 고려하십시오. 프로세서 수준에서는 분기 명령입니다.
당신은 프로세서이고 분기를 봅니다. 당신은 그것이 어느 방향으로 갈 것인지 전혀 모릅니다. 너 뭐하니? 실행을 중지하고 이전 지침이 완료 될 때까지 기다립니다. 그런 다음 올바른 경로를 계속합니다.
최신 프로세서는 복잡하고 파이프 라인이 길다. 그래서 그들은 "워밍업"과 "슬로우 다운"을 위해 영원히 걸립니다.
더 좋은 방법이 있습니까? 가지가 어느 방향으로 갈지 짐작하세요!
맞다면 계속 실행합니다.
잘못 추측했다면 파이프 라인을 플러시하고 브랜치로 롤백해야합니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.
매번 맞히면 실행을 멈출 필요가 없습니다. 너무 자주 잘못 추측하면 지연, 롤백 및 재시작에 많은 시간을 소비합니다.
이것이 분기 예측입니다. 나는 기차가 깃발로 방향을 알릴 수 있기 때문에 이것이 최고의 비유가 아니라는 것을 인정합니다. 그러나 컴퓨터에서 프로세서는 분기가 마지막 순간까지 어떤 방향으로 갈 것인지 알지 못합니다.
그렇다면 기차가 다른 경로로 후진하고 내려 가야하는 횟수를 최소화하기 위해 전략적으로 어떻게 추측 하시겠습니까? 당신은 과거의 역사를 봅니다! 기차가 99 %의 시간 동안 왼쪽으로 가면 왼쪽으로 추측합니다. 번갈아 가며 추측하면 번갈아 가며. 세 번에 한 번만 가면 똑같아요 ...
즉, 패턴을 식별하고 따르려고합니다. 이것은 분기 예측자가 작동하는 방식입니다.
대부분의 응용 프로그램에는 잘 작동하는 분기가 있습니다. 따라서 최신 분기 예측기는 일반적으로 90 % 이상의 적중률을 달성합니다. 그러나 인식 할 수없는 패턴이없는 예측할 수없는 분기에 직면하면 분기 예측자는 사실상 쓸모가 없습니다.
추가 읽기 : Wikipedia의 "지점 예측기"기사.
위에서 암시했듯이 범인은 다음과 같은 if 문입니다.
if (데이터 [c]> = 128)
합계 + = 데이터 [c];
데이터는 0과 255 사이에 균등하게 분포되어 있습니다. 데이터가 정렬 될 때 대략 반복의 전반부는 if 문을 입력하지 않습니다. 그 후에는 모두 if 문에 들어갑니다.
분기가 같은 방향으로 여러 번 연속적으로 이동하므로 분기 예측기에 매우 친숙합니다. 단순한 포화 카운터조차도 방향을 전환 한 후 몇 번의 반복을 제외하고 분기를 올바르게 예측합니다.
빠른 시각화 :
T = 취한 가지
N = 분기하지 않음
데이터 [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
분기 = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (예측하기 쉬움)
그러나 데이터가 완전히 임의적이면 임의 데이터를 예측할 수 없기 때문에 분기 예측기가 쓸모 없게됩니다. 따라서 아마도 약 50 %의 잘못된 예측이있을 것입니다 (무작위 추측보다 낫지 않음).
데이터 [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
분기 = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (완전 무작위-예측하기 어렵 음)
그래서 무엇을 할 수 있습니까?
컴파일러가 분기를 조건부 이동으로 최적화 할 수없는 경우 성능을 위해 가독성을 희생하려는 경우 몇 가지 해킹을 시도 할 수 있습니다.
바꾸다:
if (데이터 [c]> = 128)
합계 + = 데이터 [c];
와:
int t = (데이터 [c]-128) >> 31;
합계 + = ~ t & 데이터 [c];
이렇게하면 분기가 제거되고 일부 비트 연산으로 대체됩니다.
(이 해킹은 원래의 if 문과 완전히 동일하지는 않지만이 경우 data []의 모든 입력 값에 대해 유효합니다.)
벤치 마크 : Core i7 920 @ 3.5GHz
C ++-Visual Studio 2010-x64 릴리스
// 분기-임의
초 = 11.777
// 분기-정렬 됨
초 = 2.352
// 분기 없음-무작위
초 = 2.564
// 분기 없음-정렬 됨
초 = 2.587
자바-NetBeans 7.1.1 JDK 7-x64
// 분기-임의
초 = 10.93293813
// 분기-정렬 됨
초 = 5.643797077
// 분기 없음-랜덤
초 = 3.113581453
// 분기 없음-정렬 됨
초 = 3.186068823
관찰 :
분기 사용 : 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.
Hack 사용 : 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 차이가 없습니다.
C ++의 경우 해킹은 실제로 데이터가 정렬 될 때 브랜치보다 약간 느립니다.
일반적인 경험 법칙은 중요한 루프 (예 :이 예)에서 데이터 종속 분기를 피하는 것입니다.
최신 정보:
x64에서 -O3 또는 -ftree-vectorize를 사용하는 GCC 4.6.1은 조건부 이동을 생성 할 수 있습니다. 따라서 정렬 된 데이터와 정렬되지 않은 데이터간에 차이가 없습니다. 둘 다 빠릅니다.
(또는 다소 빠름 : 이미 분류 된 경우의 경우, 특히 GCC가 추가하는 대신 중요 경로에 배치하는 경우 특히 cmov가 2주기 지연이있는 Broadwell 이전의 Intel에서 cmov가 느려질 수 있습니다. gcc 최적화 플래그 -O3는 코드를 느리게 만듭니다. -O2보다)
VC ++ 2010은 / Ox에서도이 분기에 대한 조건부 이동을 생성 할 수 없습니다.
인텔 C ++ 컴파일러 (ICC) 11은 기적적인 일을합니다. 두 루프를 교환하여 예측할 수없는 분기를 외부 루프로 끌어 올립니다. 따라서 잘못된 예측에 영향을받지 않을뿐만 아니라 VC ++ 및 GCC가 생성 할 수있는 것보다 두 배나 빠릅니다! 즉, ICC는 테스트 루프를 활용하여 벤치 마크를 무너 뜨 렸습니다.
인텔 컴파일러에 분기없는 코드를 제공하면 완전히 벡터화하고 분기와 마찬가지로 빠릅니다 (루프 교환 사용).
이것은 성숙한 현대 컴파일러조차도 코드를 최적화하는 능력이 크게 다를 수 있음을 보여줍니다.
|
분기 예측.
정렬 된 배열의 경우 조건 data [c]> = 128은 연속 된 값에 대해 먼저 거짓이되고 이후의 모든 값에 대해 참이됩니다. 예측하기 쉽습니다. 정렬되지 않은 어레이를 사용하면 분기 비용을 지불합니다.
|
데이터를 정렬 할 때 성능이 크게 향상되는 이유는 Mysticial의 답변에서 아름답게 설명했듯이 분기 예측 패널티가 제거 되었기 때문입니다.
이제 코드를 보면
if (데이터 [c]> = 128)
합계 + = 데이터 [c];
이 특정 if ... else ... 브랜치의 의미는 조건이 충족 될 때 무언가를 추가하는 것임을 알 수 있습니다. 이러한 유형의 분기는 x86 시스템에서 조건부 이동 명령 인 cmovl로 컴파일되는 조건부 이동 문으로 쉽게 변환 될 수 있습니다. 분기 및 잠재적 분기 예측 패널티가 제거됩니다.
C, 따라서 C ++에서 x86의 조건부 이동 명령어로 직접 (최적화없이) 컴파일되는 명령문은 삼항 연산자 ...? ... : .... 따라서 위의 문장을 동등한 것으로 다시 작성합니다.
합계 + = 데이터 [c]> = 128? 데이터 [c] : 0;
가독성을 유지하면서 속도 향상 요소를 확인할 수 있습니다.
Intel Core i7-2600K @ 3.4GHz 및 Visual Studio 2010 릴리스 모드에서 벤치 마크는 다음과 같습니다 (Mysticial에서 복사 한 형식).
x86
// 분기-임의
초 = 8.885
// 분기-정렬 됨
초 = 1.528
// 분기 없음-무작위
초 = 3.716
// 분기 없음-정렬 됨
초 = 3.71
x64
// 분기-임의
초 = 11.302
// 분기-정렬 됨
초 = 1.830
// 분기 없음-무작위
초 = 2.736
// 분기 없음-정렬 됨
초 = 2.737
결과는 여러 테스트에서 강력합니다. 분기 결과를 예측할 수 없으면 속도가 크게 향상되지만 예측할 수 있으면 약간의 어려움이 있습니다. 실제로 조건부 이동을 사용하면 데이터 패턴에 관계없이 성능이 동일합니다.
이제 그들이 생성하는 x86 어셈블리를 조사하여 더 자세히 살펴 보겠습니다. 간단하게하기 위해 max1과 max2의 두 가지 함수를 사용합니다.
max1은 다음과 같은 경우 조건부 분기를 사용합니다.
int max1 (int a, int b) {
만약 (a> b)
반환 a;
그밖에
반환 b;
}
max2는 삼항 연산자를 사용합니다 ...? ... : ... :
int max2 (int a, int b) {
반환 a> b? a : b;
}
x86-64 컴퓨터에서 GCC -S는 아래 어셈블리를 생성합니다.
: max1
movl % edi, -4 (% rbp)
movl % esi, -8 (% rbp)
movl -4 (% rbp), % eax
cmpl -8 (% rbp), % eax
jle .L2
movl -4 (% rbp), % eax
movl % eax, -12 (% rbp)
jmp .L4
.L2 :
movl -8 (% rbp), % eax
movl % eax, -12 (% rbp)
.L4 :
movl -12 (% rbp), % eax
떠나다
ret
: max2
movl % edi, -4 (% rbp)
movl % esi, -8 (% rbp)
movl -4 (% rbp), % eax
cmpl % eax, -8 (% rbp)
cmovge -8 (% rbp), % eax
떠나다
ret
max2는 cmovge 명령 사용으로 인해 훨씬 ​​적은 코드를 사용합니다. 그러나 실제 이득은 max2가 분기 점프, jmp를 포함하지 않는다는 것입니다. 이는 예측 된 결과가 옳지 않은 경우 상당한 성능 저하를 가져옵니다.
그렇다면 조건부 이동이 더 나은 이유는 무엇입니까?
일반적인 x86 프로세서에서 명령어 실행은 여러 단계로 나뉩니다. 대략, 우리는 다른 단계를 처리하기 위해 다른 하드웨어를 가지고 있습니다. 따라서 새로운 명령을 시작하기 위해 하나의 명령이 완료 될 때까지 기다릴 필요가 없습니다. 이를 파이프 라이닝이라고합니다.
분기의 경우 다음 명령어는 이전 명령어에 의해 결정되므로 파이프 라이닝을 수행 할 수 없습니다. 우리는 기다리거나 예측해야합니다.
조건부 이동 사례에서실행 조건부 이동 명령은 여러 단계로 나뉘지만 Fetch 및 Decode와 같은 이전 단계는 이전 명령의 결과에 의존하지 않습니다. 후반 단계에서만 결과가 필요합니다. 따라서 우리는 하나의 명령어 실행 시간의 일부를 기다립니다. 이것이 예측이 쉬울 때 조건부 이동 버전이 분기보다 느린 이유입니다.
Computer Systems : A Programmer 's Perspective, 제 2 판에서는 이에 대해 자세히 설명합니다. 조건부 이동 명령에 대해서는 섹션 3.6.6, 프로세서 아키텍처에 대해서는 4 장 전체, 분기 예측 및 잘못된 예측 페널티에 대한 특별 처리에 대해서는 섹션 5.11.2를 확인할 수 있습니다.
일부 최신 컴파일러는 더 나은 성능으로 어셈블리에 맞게 코드를 최적화 할 수 있으며, 일부 컴파일러는 그렇지 않을 수 있습니다 (문제의 코드는 Visual Studio의 네이티브 컴파일러를 사용함). 예측할 수 없을 때 분기와 조건부 이동 간의 성능 차이를 알면 시나리오가 너무 복잡해져 컴파일러가 자동으로 최적화 할 수 없을 때 더 나은 성능으로 코드를 작성할 수 있습니다.
|
이 코드에 수행 할 수있는 더 많은 최적화에 대해 궁금한 경우 다음을 고려하십시오.
원래 루프로 시작 :
for (부호없는 i = 0; i <100000; ++ i)
{
for (부호없는 j = 0; j  = 128)
합계 + = 데이터 [j];
}
}
루프 교환을 사용하면이 루프를 다음과 같이 안전하게 변경할 수 있습니다.
for (부호없는 j = 0; j  = 128)
합계 + = 데이터 [j];
}
}
그런 다음 i 루프를 실행하는 동안 if 조건이 일정하다는 것을 알 수 있으므로 if out을 호이스트 할 수 있습니다.
for (부호없는 j = 0; j  = 128)
{
for (부호없는 i = 0; i <100000; ++ i)
{
합계 + = 데이터 [j];
}
}
}
그런 다음 부동 소수점 모델이 허용한다고 가정하면 내부 루프가 하나의 단일 표현식으로 축소 될 수 있음을 알 수 있습니다 (예 : / fp : fast가 throw 됨).
for (부호없는 j = 0; j  = 128)
{
합계 + = 데이터 [j] * 100000;
}
}
그것은 이전보다 100,000 배 더 빠릅니다.
|
의심 할 여지없이 우리 중 일부는 CPU의 분기 예측 자에 문제가되는 코드를 식별하는 방법에 관심이있을 것입니다. Valgrind 도구 cachegrind에는 --branch-sim = yes 플래그를 사용하여 활성화 된 분기 예측 시뮬레이터가 있습니다. 이 질문의 예제에서 외부 루프 수를 10000 개로 줄이고 g ++로 컴파일하여 실행하면 다음과 같은 결과가 나타납니다.
정렬 :
== 32551 == 지점 : 656,645,130 (656,609,208 cond + 35,922 ind)
== 32551 == 잘못된 예측 : 169,556 (169,095 cond + 461 ind)
== 32551 == 잘못된 비율 : 0.0 % (0.0 % + 1.2 %)
분류되지 않음 :
== 32555 == 지점 : 655,996,082 (655,960,160 cond + 35,922 ind)
== 32555 == 잘못된 예측 : 164,073,152 (164,072,692 cond + 460 ind)
== 32555 == 잘못된 비율 : 25.0 % (25.0 % + 1.2 %)
cg_annotate에 의해 생성 된 라인 별 출력으로 드릴 다운하면 해당 루프를 볼 수 있습니다.
정렬 :
Bc Bcm Bi Bim
10,001 40 0 ​​for (unsigned i = 0; i <10000; ++ i)
. . . . {
. . . . // 기본 루프
327,690,000 10,016 0 0 for (unsigned c = 0; c  = 128)
0 0 0 0 합계 + = 데이터 [c];
. . . . }
. . . . }
분류되지 않음 :
Bc Bcm Bi Bim
10,001 40 0 ​​(부호없는 i = 0; i <10000; ++ i)
. . . . {
. . . . // 기본 루프
327,690,000 10,038 0 0 for (unsigned c = 0; c  = 128)
0 0 0 0 합계 + = 데이터 [c];
. . . . }
. . . . }
이렇게하면 문제가있는 줄을 쉽게 식별 할 수 있습니다. 정렬되지 않은 버전에서는 if (data [c]> = 128) 줄이 cachegrind의 분기 예측 자 모델에서 164,050,007 개의 잘못된 조건부 분기 (Bcm)를 유발하는 반면 정렬 된 버전에서는 10,006 만 발생합니다. .
또는 Linux에서 성능 카운터 하위 시스템을 사용하여 동일한 작업을 수행 할 수 있지만 CPU 카운터를 사용하는 기본 성능을 사용할 수 있습니다.
성능 통계 ./sumtest_sorted
정렬 :
'./sumtest_sorted'에 대한 성능 카운터 통계 :
11808.095776 작업 클럭 # 0.998 CPU 사용
1,062 개의 컨텍스트 스위치 # 0.090 K / sec
14 개의 CPU 마이그레이션 # 0.001K / 초
337 페이지 오류 # 0.029 K / sec
26,487,882,764 사이클 # 2.243GHz
41,025,654,322 명령 # 1.55 insns per cycle
6,558,871,379 개 지점 # 555.455 M / sec
567,204 개의 분기 누락 # 모든 분기의 0.01 %
11.827228330 초 경과
분류되지 않음 :
공연'./sumtest_unsorted'에 대한 카운터 통계 :
28877.954344 작업 클럭 # 0.998 CPU 사용
2,584 개의 컨텍스트 스위치 # 0.089 K / sec
18 CPU 마이그레이션 # 0.001K / 초
335 페이지 오류 # 0.012 K / sec
65,076,127,595주기 # 2.253 GHz
41,032,528,741 명령어 # 사이클 당 0.63 insns
6,560,579,013 분기 # 227.183 M / sec
1,646,394,749 개의 분기 누락 # 모든 분기의 25.10 %
28.935500947 초 경과
디스 어셈블리로 소스 코드 주석을 달 수도 있습니다.
성능 기록 -e 분기 누락 ./sumtest_unsorted
perf 주석 -d sumtest_unsorted
퍼센트 | sumtest_unsorted의 소스 코드 및 디스 어셈블리
------------------------------------------------
...
: 합계 + = 데이터 [c];
0.00 : 400a1a : mov -0x14 (% rbp), % eax
39.97 : 400a1d : 이동 % eax, % eax
5.31 : 400a1f : mov -0x20040 (% rbp, % rax, 4), % eax
4.60 : 400a26 : cltq
0.00 : 400a28 : % rax, -0x30 (% rbp) 추가
...
자세한 내용은 성능 자습서를 참조하십시오.
|
이 질문과 그에 대한 답을 읽었는데 답이 없다고 느낍니다.
관리 언어에서 특히 잘 작동하는 것으로 확인 된 분기 예측을 제거하는 일반적인 방법은 분기를 사용하는 대신 테이블 조회입니다 (이 경우에는 테스트하지 않았지만).
이 접근 방식은 일반적으로 다음과 같은 경우에 적용됩니다.
작은 테이블이며 프로세서에 캐시 될 가능성이 높습니다.
매우 타이트한 루프에서 작업을 실행 중이거나 프로세서가 데이터를 미리로드 할 수 있습니다.
배경과 이유
프로세서 관점에서 보면 메모리가 느립니다. 속도 차이를 보완하기 위해 두 개의 캐시가 프로세서 (L1 / L2 캐시)에 내장되어 있습니다. 그래서 당신이 당신의 멋진 계산을하고 있고 당신이 메모리 조각이 필요하다는 것을 알아 내고 있다고 상상 해보세요. 프로세서는 '로드'작업을 수행하고 메모리 조각을 캐시에로드 한 다음 캐시를 사용하여 나머지 계산을 수행합니다. 메모리가 상대적으로 느리기 때문에이 '로드'는 프로그램 속도를 늦 춥니 다.
분기 예측과 마찬가지로 이것은 펜티엄 프로세서에서 최적화되었습니다. 프로세서는 데이터를로드해야한다고 예측하고 작업이 실제로 캐시에 도달하기 전에이를 캐시에로드하려고합니다. 이미 살펴 보았 듯이 분기 예측은 때때로 끔찍하게 잘못됩니다. 최악의 시나리오에서는 다시 돌아가서 실제로 메모리로드를 기다려야합니다. 이는 영원히 걸릴 것입니다 (즉, 분기 예측 실패는 좋지 않습니다. 분기 예측 실패 후로드는 끔찍합니다!).
다행스럽게도 메모리 액세스 패턴을 예측할 수있는 경우 프로세서는이를 빠른 캐시에로드하고 모든 것이 정상입니다.
가장 먼저 알아야 할 것은 작은 것이 무엇입니까? 일반적으로 작을수록 더 좋지만, 일반적으로 크기가 <= 4096 바이트 인 조회 테이블을 사용하는 것이 좋습니다. 상한으로 : 조회 테이블이 64K보다 큰 경우 다시 고려할 가치가 있습니다.
테이블 구성
그래서 우리는 작은 테이블을 만들 수 있다는 것을 알아 냈습니다. 다음으로 할 일은 검색 기능을 제자리에 가져 오는 것입니다. 조회 함수는 일반적으로 몇 가지 기본 정수 연산 (및 또는 xor, 이동, 추가, 제거 및 곱하기)을 사용하는 작은 함수입니다. 조회 기능을 통해 입력 한 내용을 테이블의 일종의 '고유 키'로 변환하고 싶을 때 원하는 모든 작업에 대한 답을 제공합니다.
이 경우 :> = 128은 값을 유지할 수 있음을 의미하고 <128은 값을 제거함을 의미합니다. 이를 수행하는 가장 쉬운 방법은 'AND'를 사용하는 것입니다. 유지하면 7FFFFFFF로 AND합니다. 우리가 그것을 없애고 싶다면, 우리는 그것을 0으로 AND합니다. 또한 128은 2의 거듭 제곱이라는 것을 알 수 있습니다. 그래서 계속해서 32768/128 정수 테이블을 만들고 하나의 0으로 채울 수 있습니다. 7FFFFFFFF.
관리 언어
이것이 관리되는 언어에서 왜 잘 작동하는지 궁금 할 것입니다. 결국 관리 언어는 분기로 어레이의 경계를 확인하여 엉망이되지 않도록합니다.
글쎄, 정확히는 ... :-)
관리되는 언어에 대해이 분기를 제거하기위한 작업이 많이있었습니다. 예를 들면 :
for (int i = 0; i  = 128)? c : 0;
}
// 테스트
DateTime startTime = System.DateTime.Now;
장기 합계 = 0;
for (int i = 0; i <100000; ++ i)
{
// 기본 루프
for (int j = 0; j > 7);
a [j] + = 데이터 [c];
}
}
double elapsedTime = static_cast  (clock ()-시작) / CLOCKS_PER_SEC;
합계 = a [1];
이 코드는 추가의 절반을 낭비하지만 분기 예측 실패는 없습니다. 실제 if 문이있는 버전보다 무작위 데이터에서 엄청나게 빠릅니다.
그러나 내 테스트에서 명시 적 조회 테이블은 이것보다 약간 더 빠릅니다. 아마도 조회 테이블로의 인덱싱이 비트 이동보다 약간 빠르기 때문일 것입니다. 이것은 내 코드가 조회 테이블을 설정하고 사용하는 방법을 보여줍니다 (코드에서 "LookUp Table"에 대해 상상할 수 없을 정도로 lut이라고 함). 다음은 C ++ 코드입니다.
// 룩업 테이블을 선언하고 채 웁니다.
int lut [256];
for (부호없는 c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c : 0;
// 빌드 후 조회 테이블 사용
for (부호없는 i = 0; i <100000; ++ i)
{
// 기본 루프
for (부호없는 c = 0; c  값)
노드 = 노드-> pLeft;
그밖에
노드 = 노드-> pRight;
이 라이브러리는 다음과 같은 작업을 수행합니다.
i = (x <노드-> 값);
노드 = 노드-> 링크 [i];
다음은이 코드에 대한 링크입니다. Red Black Trees, Eternally Confuzzled
|
정렬 된 경우 성공적인 분기 예측 또는 분기없는 비교 트릭에 의존하는 것보다 더 잘할 수 있습니다. 분기를 완전히 제거하십시오.
실제로 배열은 데이터가 128 미만이고 데이터가 128 이상인 인접 영역에서 분할됩니다. 따라서 이분법 검색 (Lg (arraySize) = 15 비교 사용)으로 분할 지점을 찾은 다음 다음에서 직선 누적을 수행해야합니다. 그 지점.
(선택 안 함)
int i = 0, j, k = arraySize;
동안 (i > 1;
if (데이터 [j]> = 128)
k = j;
그밖에
i = j;
}
합계 = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k : i) = j)
j = (i + k) >> 1;
for (sum = 0; i  = 128)
/ \
/ \
/ \
허위 사실
/ \
/ \
/ \
/ \
B) 합계 + = 데이터 [c]; C) for 루프 또는 print ().
분기 예측이 없으면 다음이 발생합니다.
명령 B 또는 명령 C를 실행하려면 명령 A가 명령 B 또는 명령 C로 이동하는 결정이 명령 A의 결과에 따라 달라 지므로 명령 A가 파이프 라인의 EX 단계까지 도달하지 않을 때까지 기다려야합니다. 따라서 파이프 라인 이렇게 보일 것입니다.
조건이 true를 반환하는 경우 :
조건이 거짓을 반환하는 경우 :
명령 A의 결과를 기다린 결과, 위의 경우에 소비 된 총 CPU 사이클 (분기 예측 없음, 참 및 거짓 모두)은 7입니다.
그렇다면 분기 예측이란 무엇입니까?
분기 예측자는 이것이 확실하게 알려지기 전에 분기 (if-then-else 구조)가 어느 방향으로 이동할지 추측하려고합니다. 명령 A가 파이프 라인의 EX 단계에 도달 할 때까지 기다리지 않지만 결정을 추측하고 해당 명령으로 이동합니다 (이 예의 경우 B 또는 C).
정확한 추측의 경우 파이프 라인은 다음과 같습니다.
나중에 추측이 잘못되었다는 것이 감지되면 부분적으로 실행 된 명령어가 삭제되고 파이프 라인이 올바른 분기로 다시 시작되어 지연이 발생합니다.
분기 예측 오류의 경우 낭비되는 시간은 가져 오기 단계에서 실행 단계까지 파이프 라인의 단계 수와 같습니다. 최신 마이크로 프로세서는 파이프 라인이 상당히 길어 예측 오류 지연이 10 ~ 20 클럭 사이클 사이입니다. 파이프 라인이 길수록 좋은 분기 예측자가 더 많이 필요합니다.
OP의 코드에서 처음 조건부, 분기 예측자는 예측을 기반으로하는 정보가 없으므로 처음에는 다음 명령어를 무작위로 선택합니다. 나중에 for 루프에서 히스토리를 기반으로 예측할 수 있습니다.
오름차순으로 정렬 된 배열의 경우 다음 세 가지 가능성이 있습니다.
모든 요소가 128 미만입니다.
모든 요소가 128보다 큽니다.
일부 시작하는 새 요소가 128보다 작다가 나중에 128보다 커집니다.
예측자가 첫 번째 실행에서 항상 실제 분기를 가정한다고 가정 해 보겠습니다.
따라서 첫 번째 경우에는 항상역사적으로 모든 예측이 정확하기 때문에 분기합니다.
두 번째 경우에는 처음에는 잘못 예측하지만 몇 번 반복하면 올바르게 예측됩니다.
세 번째 경우에는 요소가 128 미만이 될 때까지 처음에 올바르게 예측합니다. 그 후 얼마 동안 실패하고 기록에서 분기 예측 실패를 확인하면 자체적으로 수정됩니다.
이러한 모든 경우에 실패 횟수가 너무 적어 결과적으로 몇 번만 부분적으로 실행 된 명령을 버리고 올바른 분기로 다시 시작하면 CPU주기가 줄어 듭니다.
그러나 정렬되지 않은 임의의 배열의 경우 예측은 부분적으로 실행 된 명령어를 버리고 대부분의 경우 올바른 분기로 다시 시작해야하며 정렬 된 배열에 비해 CPU주기가 더 많이 발생합니다.
|
공식적인 답변은
인텔-지점 오류 예측 비용 방지
Intel-잘못된 예측을 방지하기위한 분기 및 루프 재구성
과학 논문-분기 예측 컴퓨터 아키텍처
서적 : J.L. Hennessy, D.A. Patterson : 컴퓨터 아키텍처 : 정량적 접근
과학 출판물의 기사 : T.Y. 예, Y.N. Patt는 분기 예측에 대해 많은 것을 만들었습니다.
이 멋진 다이어그램에서 분기 예측기가 혼란스러워지는 이유를 볼 수도 있습니다.
원본 코드의 각 요소는 임의의 값입니다.
데이터 [c] = std :: rand () % 256;
따라서 예측자는 std :: rand () 타격으로 변을 바꿉니다.
반면에, 일단 정렬되면 예측자는 먼저 강하게 취해지지 않은 상태로 이동하고 값이 높은 값으로 변경되면 예측자는 강하게 취해지지 않음에서 강하게 취함에 이르기까지 세 번의 변화를 거치게됩니다.
|
같은 줄에서 (나는 이것이 어떤 대답으로도 강조되지 않았다고 생각합니다) 때때로 (특히 성능이 중요한 소프트웨어에서 – Linux 커널에서와 같이) 다음과 같은 if 문을 찾을 수 있다는 점을 언급하는 것이 좋습니다.
if (likely (everything_is_ok))
{
/ * 무언가를하십시오 * /
}
또는 유사하게 :
if (unlikely (very_improbable_condition))
{
/ * 무언가를하십시오 * /
}
chance ()와 likely ()는 실제로 GCC의 __builtin_expect와 같은 것을 사용하여 정의 된 매크로로 컴파일러가 사용자가 제공 한 정보를 고려하여 조건에 유리하도록 예측 코드를 삽입 할 수 있도록 도와줍니다. GCC는 실행중인 프로그램의 동작을 변경하거나 캐시 지우기 등과 같은 낮은 수준의 명령을 내릴 수있는 다른 내장 기능을 지원합니다. 사용 가능한 GCC 내장 기능을 살펴 보는이 문서를 참조하세요.
일반적으로 이러한 종류의 최적화는 주로 실행 시간이 중요하고 중요한 하드 실시간 애플리케이션 또는 임베디드 시스템에서 발견됩니다. 예를 들어, 1/10000000 번만 발생하는 오류 조건을 확인하는 경우 컴파일러에 이에 대해 알리지 않는 이유는 무엇입니까? 이렇게하면 기본적으로 분기 예측에서 조건이 거짓이라고 가정합니다.
|
C ++에서 자주 사용되는 부울 연산은 컴파일 된 프로그램에서 많은 분기를 생성합니다. 이러한 분기가 루프 내부에 있고 예측하기 어려운 경우 실행 속도가 크게 느려질 수 있습니다. 부울 변수는 8 비트 정수로 저장되며 false는 0이고 true는 1입니다.
부울 변수는 입력으로 부울 변수가있는 모든 연산자가 입력에 0 또는 1이 아닌 다른 값이 있는지 확인한다는 의미에서 과도하게 결정되지만 출력으로 부울이있는 연산자는 0 또는 1 이외의 값을 생성 할 수 없습니다. 입력으로서의 부울 변수는 필요보다 덜 효율적입니다.
예를 고려하십시오.
bool a, b, c, d;
c = a && b;
d = a || 비;
이것은 일반적으로 다음과 같은 방식으로 컴파일러에 의해 구현됩니다.
bool a, b, c, d;
if (a! = 0) {
if (b! = 0) {
c = 1;
}
else {
CFALSE로 이동;
}
}
else {
CFALSE :
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
else {
DTRUE로 이동합니다.
}
}
else {
DTRUE :
d = 1;
}
이 코드는 최적이 아닙니다. 예측이 잘못 될 경우 지점에 시간이 오래 걸릴 수 있습니다. 피연산자에 0과 1 이외의 다른 값이 없다는 것이 확실하다면 부울 연산을 훨씬 더 효율적으로 만들 수 있습니다. 컴파일러가 이러한 가정을하지 않는 이유는 변수가 초기화되지 않은 경우 다른 값을 가질 수 있기 때문입니다. 또는 알려지지 않은 출처에서 왔습니다. 위 코드는 a와 b가 유효한 값으로 초기화되었거나 부울 출력을 생성하는 연산자에서 온 경우 최적화 할 수 있습니다. 최적화 된 코드는 다음과 같습니다.
문자 a = 0, b = 1, c, d;
c = a & b;
d = a | 비;
부울 연산자 (&& 및 ||) 대신 비트 연산자 (& 및 |)를 사용할 수 있도록 부울 대신 char가 사용됩니다. 비트 연산자는 하나의 클럭 사이클 만 사용하는 단일 명령어입니다. OR 연산자 (|)는 a와 b가 0 또는 1이 아닌 다른 값을 가지더라도 작동합니다. AND 연산자 (&)와 EXCLUSIVE OR 연산자 (^)는 피연산자가 0과 1이 아닌 다른 값을 가질 경우 일관성없는 결과를 제공 할 수 있습니다.
~ NOT에는 사용할 수 없습니다. 대신0 또는 1로 알려진 변수에 대해 1로 XOR 처리하여 부울 NOT을 만들 수 있습니다.
bool a, b;
b =! a;
다음과 같이 최적화 할 수 있습니다.
문자 a = 0, b;
b = a ^ 1;
a && b는 a가 거짓이면 평가되지 않아야하는 표현식 인 경우 a & b로 대체 될 수 없습니다 (&&는 b를 평가하지 않고 & will). 마찬가지로, a || b는 a | b 인 경우 b가 a가 참이면 평가되지 않아야하는 표현식입니다.
비트 연산자를 사용하면 피연산자가 비교 인 경우보다 피연산자가 변수 인 경우 더 유리합니다.
bool a; 이중 x, y, z;
a = x> y && z <5.0;
대부분의 경우에 최적입니다 (&& 표현식이 많은 분기 잘못된 예측을 생성 할 것으로 예상하지 않는 한).
|
그건 확실합니다!...
분기 예측은 코드에서 발생하는 전환으로 인해 로직 실행을 느리게 만듭니다! 직선 거리 또는 회전이 많은 거리를가는 것과 같습니다. 직선 거리가 더 빨리 완료 될 것입니다! ...
배열이 정렬 된 경우 첫 번째 단계에서 조건이 거짓입니다. data [c]> = 128, 그러면 거리 끝까지의 전체 길이에 대한 참 값이됩니다. 이것이 논리의 끝까지 더 빨리 도달하는 방법입니다. 반면에 정렬되지 않은 배열을 사용하면 코드가 확실히 느리게 실행되도록 많은 회전과 처리가 필요합니다.
아래에서 내가 만든 이미지를보십시오. 어느 거리가 더 빨리 끝날까요?
따라서 프로그래밍 방식으로 분기 예측으로 인해 프로세스가 느려집니다.
또한 마지막에는 각각 코드에 다르게 영향을 미칠 두 가지 종류의 분기 예측이 있다는 것을 아는 것이 좋습니다.
1. 정적
2. 동적
마이크로 프로세서에서 처음으로 정적 분기 예측을 사용합니다.
조건부 분기가 발생하고 동적 분기 예측이
조건부 분기 코드의 후속 실행에 사용됩니다.
이러한 기능을 활용하기 위해 코드를 효과적으로 작성하려면
규칙, if-else 또는 switch 문을 작성할 때 가장
일반적인 경우를 먼저 확인하고 점진적으로 가장 적은 빈도로 작업합니다.
루프는 특별한 코드 순서를 요구하지 않습니다.
루프 반복기의 조건 인 정적 분기 예측
일반적으로 사용됩니다.
|
이 질문은 이미 여러 번 훌륭하게 답변되었습니다. 그래도 또 다른 흥미로운 분석에 그룹의 관심을 끌고 싶습니다.
최근에이 예제 (매우 약간 수정 됨)는 Windows에서 프로그램 자체 내에서 코드 조각을 프로파일 링하는 방법을 보여주는 방법으로도 사용되었습니다. 그 과정에서 저자는 또한 결과를 사용하여 정렬 된 경우와 정렬되지 않은 경우 모두에서 코드가 대부분의 시간을 보내는 위치를 확인하는 방법을 보여줍니다. 마지막으로 HAL (Hardware Abstraction Layer)의 잘 알려진 기능을 사용하여 분류되지 않은 경우에 분기 오예가 얼마나 많이 발생하는지 확인하는 방법도 보여줍니다.
링크는 다음과 같습니다.
자체 프로파일 링 시연
|
다른 사람들이 이미 언급했듯이 미스터리 뒤에는 Branch Predictor가 있습니다.
나는 무언가를 추가하려는 것이 아니라 개념을 다른 방식으로 설명하고 있습니다.
텍스트와 다이어그램을 포함하는 간결한 소개가 위키에 있습니다.
분기 예측자를 직관적으로 정교화하기 위해 다이어그램을 사용하는 아래 설명을 좋아합니다.
컴퓨터 아키텍처에서 분기 예측기는
분기가 어느 방향인지 추측하는 디지털 회로 (예 :
if-then-else 구조)가 확실히 알려지기 전에 진행됩니다. 그만큼
분기 예측기의 목적은
명령 파이프 라인. 분기 예측자는 다음에서 중요한 역할을합니다.
많은 최신 파이프 라인에서 높은 효과적인 성능 달성
x86과 같은 마이크로 프로세서 아키텍처.
양방향 분기는 일반적으로 조건부 점프로 구현됩니다.
교수. 조건부 점프는 "취하지 않고"계속할 수 있습니다.
바로 뒤에 오는 코드의 첫 번째 분기로 실행
조건부 점프 후 또는 "취득"하여 점프 할 수 있습니다.
두 번째 코드 분기가있는 프로그램 메모리의 다른 위치
저장. 조건부 점프가 될지는 확실하지 않습니다.
조건이 계산되고
조건부 점프가 명령어의 실행 단계를 통과했습니다.
파이프 라인 (그림 1 참조).
설명 된 시나리오를 기반으로 다양한 상황에서 파이프 라인에서 명령이 실행되는 방법을 보여주는 애니메이션 데모를 작성했습니다.
분기 예측 자없이.
분기 예측이 없으면 프로세서는
조건부 점프 명령이 실행 단계를 통과했습니다.
다음 명령어는 파이프 라인의 가져 오기 단계로 들어갈 수 있습니다.
이 예제에는 세 개의 명령어가 포함되어 있고 첫 번째 명령어는 조건부 점프 명령어입니다. 후자의 두 명령은 조건부 점프 명령이 실행될 때까지 파이프 라인으로 이동할 수 있습니다.
3 개의 명령이 완료 되려면 9 클럭 사이클이 필요합니다.
분기 예측기를 사용하고 조건부 점프를하지 마십시오. 예측이조건부 점프.
3 개의 명령이 완료 되려면 7 클럭 사이클이 필요합니다.
분기 예측기를 사용하고 조건부 점프를 수행하십시오. 예측이 조건부 점프를하지 않는다고 가정 해 봅시다.
3 개의 명령이 완료 되려면 9 클럭 사이클이 필요합니다.
분기 오류 예측시 낭비되는 시간은 다음과 같습니다.
가져 오기 단계에서 파이프 라인의 단계 수
실행 단계. 최신 마이크로 프로세서는
잘못된 예측 지연이 10 ~ 20 클럭 사이가되도록 파이프 라인
사이클. 결과적으로 파이프 라인을 더 길게 만들면
고급 분기 예측기.
보시다시피 Branch Predictor를 사용하지 않을 이유가없는 것 같습니다.
Branch Predictor의 매우 기본적인 부분을 명확히하는 아주 간단한 데모입니다. 해당 gif가 성가신 경우 답변에서 자유롭게 제거하고 방문자는 BranchPredictorDemo에서 라이브 데모 소스 코드를 얻을 수도 있습니다.
|
분기 예측 이득!
분기 예측 오류가 프로그램 속도를 늦추지 않는다는 것을 이해하는 것이 중요합니다. 누락 된 예측의 비용은 분기 예측이 존재하지 않고 실행할 코드를 결정하기 위해 표현식 평가를 기다린 것과 같습니다 (다음 단락에서 추가 설명).
if (표현식)
{
// 실행 1
} else {
// 실행 2
}
if-else \ switch 문이있을 때마다 어떤 블록이 실행되어야하는지 결정하기 위해 표현식을 평가해야합니다. 컴파일러에서 생성 된 어셈블리 코드에 조건부 분기 명령어가 삽입됩니다.
분기 명령어는 컴퓨터가 다른 명령어 시퀀스를 실행하기 시작하도록하여 일부 조건에 따라 순서대로 명령어를 실행하는 기본 동작에서 벗어날 수 있습니다 (즉, 표현식이 거짓이면 프로그램은 if 블록의 코드를 건너 뜁니다). 우리의 경우 표현 평가입니다.
즉, 컴파일러는 실제로 평가되기 전에 결과를 예측하려고합니다. if 블록에서 명령어를 가져오고 표현식이 참이면 훌륭합니다! 우리는 그것을 평가하는 데 걸리는 시간을 확보하고 코드를 개선했습니다. 그렇지 않으면 잘못된 코드를 실행하고 파이프 라인이 플러시되고 올바른 블록이 실행됩니다.
심상:
경로 1 또는 경로 2를 선택해야한다고 가정 해 보겠습니다. 파트너가지도를 확인할 때까지 기다렸다가 ##에서 멈춰 기다렸거나, 운이 좋았다면 경로 1을 선택할 수 있습니다 (경로 1이 올바른 경로입니다). 파트너가지도를 확인할 때까지 기다릴 필요가 없습니다 (지도를 확인하는 데 걸리는 시간을 절약했습니다). 그렇지 않으면 다시 돌아올 것입니다.
파이프 라인을 플러싱하는 것은 매우 빠르지 만 요즘에는이 도박을 할 가치가 있습니다. 정렬 된 데이터 또는 느리게 변경되는 데이터를 예측하는 것이 빠른 변경을 예측하는 것보다 항상 쉽고 낫습니다.
O 루트 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
루트 2 \ --------------------------------
|
ARM에서는 분기가 필요하지 않습니다. 모든 명령어에는 프로세서 상태 레지스터에서 발생할 수있는 16 개의 서로 다른 조건 중 하나를 테스트하는 4 비트 조건 필드 (비용 없음)가 있고 명령어의 조건이 다음과 같은 경우 false, 명령을 건너 뜁니다. 이렇게하면 짧은 분기의 필요성이 제거되고이 알고리즘에 대한 분기 예측 적중이 없습니다. 따라서이 알고리즘의 정렬 된 버전은 정렬의 추가 오버 헤드로 인해 ARM의 정렬되지 않은 버전보다 느리게 실행됩니다.
이 알고리즘의 내부 루프는 ARM 어셈블리 언어에서 다음과 같습니다.
MOV R0, # 0 // R0 = 합계 = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, 데이터 // R2 = 데이터 배열의 addr (이 명령어를 외부 루프 외부에 배치)
.inner_loop // 내부 루프 분기 레이블
LDRB R3, [R2, R1] // R3 = 데이터 [c]
CMP R3, # 128 // R3을 128과 비교
ADDGE R0, R0, R3 // R3> = 128이면 sum + = data [c]-분기가 필요하지 않습니다!
R1, R1, # 1 추가 // C ++
CMP R1, #arraySize // c를 arraySize와 비교
BLT inner_loop // c  ());
for (부호없는 c = 0; c  = 128 인 경우
sum = sum + data1 (j);
종료
종료
종료
toc;
ExeTimeWithSorting = toc-tic;
위 MATLAB 코드의 결과는 다음과 같습니다.
a : 경과 시간 (정렬 없음) = 3479.880861 초.
b : 경과 시간 (정렬 포함) = 2377.873098 초.
@GManNickG에서와 같이 C 코드의 결과는 다음과 같습니다.
a : 경과 시간 (정렬 없음) = 19.8761 초.
b : 경과 시간 (정렬 포함) = 7.37778 초.
이를 바탕으로 MATLAB은 정렬없이 C 구현보다 거의 175 배 느리고 정렬을 사용하면 350 배 느립니다. 즉, 분기 예측의 효과는 MATLAB 구현의 경우 1.46x, C 구현의 경우 2.7x입니다.
|
데이터를 정렬하는 데 필요한 다른 답변의 가정은 올바르지 않습니다.
다음 코드는 전체 배열을 정렬하지 않고 배열의 200 개 요소 세그먼트 만 정렬하므로 가장 빠르게 실행됩니다.
k 요소 섹션 만 정렬하면 전체 배열을 정렬하는 데 필요한 O (n.log (n)) 시간이 아닌 선형 시간 O (n)에서 전처리가 완료됩니다.
#include <알고리즘>
#include 
#include 
int main () {
int 데이터 [32768]; const int l = 데이터 크기 / 데이터 크기 [0];
for (부호없는 c = 0; c  = 128)
합계 + = 데이터 [c];
}
}
std :: cout << static_cast  (clock ()-시작) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum ="<< sum << std :: endl;
}
이것은 또한 정렬 순서와 같은 알고리즘 문제와 관련이 없음을 "증명"하며 실제로 분기 예측입니다.
|
이 질문에 대한 Bjarne Stroustrup의 답변 :
인터뷰 질문 같네요. 사실인가요? 당신은 어떻게 알겠습니까? 먼저 몇 가지 측정을 수행하지 않고 효율성에 대한 질문에 답하는 것은 좋지 않으므로 측정 방법을 아는 것이 중요합니다.
그래서 저는 백만 개의 정수 벡터로 시도해 보았고 다음을 얻었습니다.
이미 32995 밀리 초 정렬 됨
125944 밀리 초 셔플
이미 18610 밀리 초 정렬 됨
섞인 133304 밀리 초
이미 17942 밀리 초로 정렬되었습니다.
107858 밀리 초 셔플
확인하기 위해 몇 번 실행했습니다. 예, 현상은 실제입니다. 내 키 코드는 다음과 같습니다.
void run (vector  & v, const string & label)
{
자동 t0 = system_clock :: now ();
sort (v.begin (), v.end ());
자동 t1 = system_clock :: now ();
cout << 레이블
<< duration_cast <마이크로 초> (t1 — t0) .count ()
<< "밀리 초 \ n";
}
무효 tst ()
{
벡터  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "이미 정렬 됨");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "셔플 됨");
}
적어도이 컴파일러, 표준 라이브러리 및 최적화 프로그램 설정에서는 현상이 실제로 발생합니다. 구현에 따라 답변이 다를 수 있습니다. 실제로 누군가가보다 체계적인 연구를 수행했으며 (빠른 웹 검색으로 찾을 수 있음) 대부분의 구현에서 그 효과를 보여줍니다.
한 가지 이유는 분기 예측입니다. 정렬 알고리즘의 주요 작업은 "if (v [i] > 7);
a [j] + = 데이터 [c];
}
}
double elapsedTime = static_cast  (clock ()-시작) / CLOCKS_PER_SEC;
합계 = a [1];
이 코드는 추가의 절반을 낭비하지만 분기 예측 실패는 없습니다. 실제 if 문이있는 버전보다 무작위 데이터에서 엄청나게 빠릅니다.
그러나 내 테스트에서 명시 적 조회 테이블은 이것보다 약간 더 빠릅니다. 아마도 조회 테이블로의 인덱싱이 비트 이동보다 약간 빠르기 때문일 것입니다. 이것은 내 코드가 조회 테이블을 설정하고 사용하는 방법을 보여줍니다 (코드에서 "LookUp Table"에 대해 상상할 수 없을 정도로 lut이라고 함). 다음은 C ++ 코드입니다.
// 룩업 테이블을 선언하고 채 웁니다.
int lut [256];
for (부호없는 c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c : 0;
// 빌드 후 조회 테이블 사용
for (부호없는 i = 0; i <100000; ++ i)
{
// 기본 루프
for (부호없는 c = 0; c  값)
노드 = 노드-> pLeft;
그밖에
노드 = 노드-> pRight;
이 라이브러리는 다음과 같은 작업을 수행합니다.
i = (x <노드-> 값);
노드 = 노드-> 링크 [i];
그것은 좋은 해결책이며 아마도 작동 할 것입니다.
|
매우 적극적인 질문입니다. 이 질문에 답하기 위해 평판 10을 획득하십시오. 평판 요구 사항은 스팸 및 비 응답 활동으로부터이 질문을 보호하는 데 도움이됩니다.
찾고있는 답변이 아닙니까? java C ++ 성능 최적화 분기 예측 태그가 지정된 다른 질문을 찾아 보거나 직접 질문하십시오.